/*
设计思路是采用动态规划方法和贪心思想来解决硬币找零问题。
它通过初始化一个数组dp来记录凑出从0到目标金额amount所需的最少硬币数量。
dp数组中的每个元素代表对应金额的最优解，即最少硬币数。

对目标金额amount的值进行遍历，找出本次遍历能够凑出的最大币种，即找出每次遍历的最优解。
并将目标金额amount的值减去本次遍历的最优解，直到该目标金额amount的值为零，则遍历结束。

最终，通过检查数组中目标金额amount的值来确定是否能够凑出该金额，并返回相应的最少硬币数量或0（表示无法凑出）。
这种方法巧妙地利用了子问题的最优解来构建原问题的最优解，从而有效地解决了硬币找零问题。


*/
pub fn dp_rec_mc(amount: u32) -> u32 {
    // TODO: 这里写逻辑
    // todo!()
    // 定义可用的硬币面额数组
    let coins = [100, 50, 20, 10, 5, 2, 1];
    // 初始化动态规划数组，大小为 amount + 1，初始值为 u32::MAX 表示无法凑出该金额
    let mut dp = vec![u32::MAX; amount as usize + 1];
    // 设置凑出 0 元的方案数为 0
    dp[0] = 0;

    // 遍历每一种硬币
    for &coin in coins.iter() {
        // 从当前硬币面额开始，遍历到总金额
        for i in coin as usize..=amount as usize {
            // 如果当前金额减去硬币面额的方案数不是 u32::MAX，说明可以凑出该金额
            if dp[i - coin] != u32::MAX {
                // 更新当前金额的最小方案数，即选择当前硬币或不选择当前硬币的较小值
                dp[i] = dp[i].min(dp[i - coin] + 1);
            }
        }
    }

    // 如果最终 dp[amount] 仍然是 u32::MAX，说明无法凑出该金额，返回 0
    // 否则，返回凑出金额的最小硬币数量
    if dp[amount as usize] == u32::MAX {
        0 // 如果无法凑出金额，返回 0
    } else {
        dp[amount as usize]
    }
}
